General Induction over odd/even numbers

Let $P$ be a property of even nums Let $Q$ be a property of odd nums

$P$/$Q$ will hold for all even/odd nums if:

• $P(zero)$
• Whenever $n$ is even and $P(n)$ we have $Q(succ\ n)$
• Whenever $n$ is odd and $Q(n)$ we have $P(succ\ n)$

Recipe for Proof by Induction

1. Decide who to induct on
   • You must induct on a premise
   • If you’re not sure which to pick, pick the most interesting, as that’s where things are more likely to happen
2. State you’re doing a proof by induction, and on which premise
3. Complete your proof by cases
   • One case per rule
   • In your cases you can assume the other premises
   • Write down your induction hypothesis (IH)

Example

Claim

%%🖋 Edit in Excalidraw%%

Example Two

%%🖋 Edit in Excalidraw%%

Related Reading

• Guide to Proofs
• 2025-09-23 Judgements
• ATiPL Problem Sheet 1